/*
 * ORACLE PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 */

/*
 *
 *
 *
 *
 *
 * Written by Doug Lea, Bill Scherer, and Michael Scott with
 * assistance from members of JCP JSR-166 Expert Group and released to
 * the public domain, as explained at
 * http://creativecommons.org/publicdomain/zero/1.0/
 */

package java.util.concurrent;
import java.util.concurrent.locks.LockSupport;
import java.util.concurrent.locks.ReentrantLock;
import java.util.*;
import java.util.Spliterator;
import java.util.Spliterators;

/**
 * A {@linkplain BlockingQueue blocking queue} in which each insert
 * operation must wait for a corresponding remove operation by another
 * thread, and vice versa.  A synchronous queue does not have any
 * internal capacity, not even a capacity of one.  You cannot
 * {@code peek} at a synchronous queue because an element is only
 * present when you try to remove it; you cannot insert an element
 * (using any method) unless another thread is trying to remove it;
 * you cannot iterate as there is nothing to iterate.  The
 * <em>head</em> of the queue is the element that the first queued
 * inserting thread is trying to add to the queue; if there is no such
 * queued thread then no element is available for removal and
 * {@code poll()} will return {@code null}.  For purposes of other
 * {@code Collection} methods (for example {@code contains}), a
 * {@code SynchronousQueue} acts as an empty collection.  This queue
 * does not permit {@code null} elements.
 *
 * <p>Synchronous queues are similar to rendezvous channels used in
 * CSP and Ada. They are well suited for handoff designs, in which an
 * object running in one thread must sync up with an object running
 * in another thread in order to hand it some information, event, or
 * task.
 *
 * <p>This class supports an optional fairness policy for ordering
 * waiting producer and consumer threads.  By default, this ordering
 * is not guaranteed. However, a queue constructed with fairness set
 * to {@code true} grants threads access in FIFO order.
 *
 * <p>This class and its iterator implement all of the
 * <em>optional</em> methods of the {@link Collection} and {@link
 * Iterator} interfaces.
 *
 * <p>This class is a member of the
 * <a href="{@docRoot}/../technotes/guides/collections/index.html">
 * Java Collections Framework</a>.
 *
 * @since 1.5
 * @author Doug Lea and Bill Scherer and Michael Scott
 * @param <E> the type of elements held in this collection
 */
public class SynchronousQueue<E> extends AbstractQueue<E>
    implements BlockingQueue<E>, java.io.Serializable {
    private static final long serialVersionUID = -3223113410248163686L;

    /*
     * This class implements extensions of the dual stack and dual
     * queue algorithms described in "Nonblocking Concurrent Objects
     * with Condition Synchronization", by W. N. Scherer III and
     * M. L. Scott.  18th Annual Conf. on Distributed Computing,
     * Oct. 2004 (see also
     * http://www.cs.rochester.edu/u/scott/synchronization/pseudocode/duals.html).
     * The (Lifo) stack is used for non-fair mode, and the (Fifo)
     * queue for fair mode. The performance of the two is generally
     * similar. Fifo usually supports higher throughput under
     * contention but Lifo maintains higher thread locality in common
     * applications.
     *
     * A dual queue (and similarly stack) is one that at any given
     * time either holds "data" -- items provided by put operations,
     * or "requests" -- slots representing take operations, or is
     * empty. A call to "fulfill" (i.e., a call requesting an item
     * from a queue holding data or vice versa) dequeues a
     * complementary node.  The most interesting feature of these
     * queues is that any operation can figure out which mode the
     * queue is in, and act accordingly without needing locks.
     *
     * Both the queue and stack extend abstract class Transferer
     * defining the single method transfer that does a put or a
     * take. These are unified into a single method because in dual
     * data structures, the put and take operations are symmetrical,
     * so nearly all code can be combined. The resulting transfer
     * methods are on the long side, but are easier to follow than
     * they would be if broken up into nearly-duplicated parts.
     *
     * The queue and stack data structures share many conceptual
     * similarities but very few concrete details. For simplicity,
     * they are kept distinct so that they can later evolve
     * separately.
     *
     * The algorithms here differ from the versions in the above paper
     * in extending them for use in synchronous queues, as well as
     * dealing with cancellation. The main differences include:
     *
     *  1. The original algorithms used bit-marked pointers, but
     *     the ones here use mode bits in nodes, leading to a number
     *     of further adaptations.
     *  2. SynchronousQueues must block threads waiting to become
     *     fulfilled.
     *  3. Support for cancellation via timeout and interrupts,
     *     including cleaning out cancelled nodes/threads
     *     from lists to avoid garbage retention and memory depletion.
     *
     * Blocking is mainly accomplished using LockSupport park/unpark,
     * except that nodes that appear to be the next ones to become
     * fulfilled first spin a bit (on multiprocessors only). On very
     * busy synchronous queues, spinning can dramatically improve
     * throughput. And on less busy ones, the amount of spinning is
     * small enough not to be noticeable.
     *
     * Cleaning is done in different ways in queues vs stacks.  For
     * queues, we can almost always remove a node immediately in O(1)
     * time (modulo retries for consistency checks) when it is
     * cancelled. But if it may be pinned as the current tail, it must
     * wait until some subsequent cancellation. For stacks, we need a
     * potentially O(n) traversal to be sure that we can remove the
     * node, but this can run concurrently with other threads
     * accessing the stack.
     *
     * While garbage collection takes care of most node reclamation
     * issues that otherwise complicate nonblocking algorithms, care
     * is taken to "forget" references to data, other nodes, and
     * threads that might be held on to long-term by blocked
     * threads. In cases where setting to null would otherwise
     * conflict with main algorithms, this is done by changing a
     * node's link to now point to the node itself. This doesn't arise
     * much for Stack nodes (because blocked threads do not hang on to
     * old head pointers), but references in Queue nodes must be
     * aggressively forgotten to avoid reachability of everything any
     * node has ever referred to since arrival.
     */

    /**
     * Shared internal API for dual stacks and queues.
     */
    abstract static class Transferer<E> {
        /**
         * Performs a put or take.
         *
         * @param e if non-null, the item to be handed to a consumer;
         *          if null, requests that transfer return an item
         *          offered by producer.
         * @param timed if this operation should timeout
         * @param nanos the timeout, in nanoseconds
         * @return if non-null, the item provided or received; if null,
         *         the operation failed due to timeout or interrupt --
         *         the caller can distinguish which of these occurred
         *         by checking Thread.interrupted.
         *
         * E   可以为null  为null表示这个请求是一个request请求，不为null表示这个请求是一个data类型的请求
         * timed    是否响应超时，是否值得超时时间   如果为true表示响应超时并且指定超时时间
         * nanos    具体的超时时间限制   单位:纳秒
         *
         * return E  如果当前请求是一个request请求  返回值如果为null表示请求超时或被中断   如果不为null表示匹配成功
         *           如果当前请求是一个data请求  返回值不为null表示请求成功  如果为null  表示请求超时或者被中断
         */
        abstract E transfer(E e, boolean timed, long nanos);
    }

    /**
     * The number of CPUs, for spin control
     * CPU数量
     *
     * 为什么要有这个参数？
     * 如果说 当前只有一个CPU那么还需要自旋吗？
     * 答案是  肯定不需要自旋了，如果只有一个CPU那么直接把当前线程挂起就好了
     * 如果还继续自旋，去占用CPU，反而会浪费性能
     */
    static final int NCPUS = Runtime.getRuntime().availableProcessors();

    /**
     * The number of times to spin before blocking in timed waits.
     * The value is empirically derived -- it works well across a
     * variety of processors and OSes. Empirically, the best value
     * seems not to vary with number of CPUs (beyond 2) so is just
     * a constant.
     * 指定了超时时间的话   表示当前线程最大自旋次数
     * 只有一个CPU的时候 自旋次数为0
     * 当CPU大于 1个的时候  表示是多核心平台  指定超时时间后的 最大自旋次数就是 32
     * 32是一个经验  得出的值
     *
     * 为什么需要自旋的操作？
     * 因为线程  挂起  唤醒，这个过程站在CPU角度是非常消耗资源的  涉及到用户态和内核态的切换
     * 自旋的好处是  自旋期间线程会一直检查自己的状态是否被匹配到   如果自旋期间被匹配到  那么就直接返回了
     * 如果自旋 期间未被  匹配到，自旋次数达标之后  还是会被挂起的
     */
    static final int maxTimedSpins = (NCPUS < 2) ? 0 : 32;

    /**
     * The number of times to spin before blocking in untimed waits.
     * This is greater than timed value because untimed waits spin
     * faster since they don't need to check times on each spin.
     * 表示未指定超时限制时  线程等待匹配的自旋次数
     * 是指定超时限制请求  的自旋次数的 16倍
     */
    static final int maxUntimedSpins = maxTimedSpins * 16;

    /**
     * The number of nanoseconds for which it is faster to spin
     * rather than to use timed park. A rough estimate suffices.
     * 如果请求是指定超时限制的话   如果超时nanos参数是小于 1000L时  不选择挂起
     * 禁止挂起  因为这个时间太短了   挂起再唤醒的成本  太高了  所以选择疯狂自旋以避免性能浪费
     */
    static final long spinForTimeoutThreshold = 1000L;

    /**
     * Dual stack
     * 非公平模式实现的同步队列   内部数据结构是 栈
     */
    static final class TransferStack<E> extends Transferer<E> {
        /*
         * This extends Scherer-Scott dual stack algorithm, differing,
         * among other ways, by using "covering" nodes rather than
         * bit-marked pointers: Fulfilling operations push on marker
         * nodes (with FULFILLING bit set in mode) to reserve a spot
         * to match a waiting node.
         */

        /* Modes for SNodes, ORed together in node fields */
        /**
         * Node represents an unfulfilled consumer
         * 表示node类型为  请求类型
         */
        static final int REQUEST    = 0;
        /**
         * Node represents an unfulfilled producer
         * 表示 node类型为  数据类型
         */
        static final int DATA       = 1;
        /**
         * Node is fulfilling another unfulfilled DATA or REQUEST
         * 表示 node类型为 匹配中类型
         * 假设 栈顶元素为 REQUEST-NODE 当前请求类型为  DATA的话  入栈之后 会修改类型为 FULFILLING 【栈顶 & 栈顶下的一个node】
         * 假设 栈顶元素为 DATA 当前请求类型为  REQUEST-NODE的话  入栈之后 会修改类型为 FULFILLING 【栈顶 & 栈顶下的一个node】
         */
        static final int FULFILLING = 2;

        /**
         * Returns true if m has fulfilling bit set.
         * 判断当前  模式是否为  匹配中状态
         */
        static boolean isFulfilling(int m) { return (m & FULFILLING) != 0; }

        /** Node class for TransferStacks. */
        static final class SNode {
            //当前栈帧的下一个栈帧
            volatile SNode next;        // next node in stack
            //与当前node 匹配的节点
            volatile SNode match;       // the node matched to this
            //假设 当前node对应的线程  自旋期间没有匹配成功 那么node节点就需要被挂起  挂起前 waiter 保存对应线程的引用
            //方便 匹配成功 后  唤醒
            volatile Thread waiter;     // to control park/unpark
            //数据域  item不为null 表示当前node是一个  data类型
            //如果 item为null  表示当前 node是一个  request类型
            Object item;                // data; or null for REQUESTs
            //表示当前 node的模式  可选模式有  DATA REQUEST FULFILLING
            int mode;
            // Note: item and mode fields don't need to be volatile
            // since they are always written before, and read after,
            // other volatile/atomic operations.

            SNode(Object item) {
                this.item = item;
            }

            /**
             * cas方式设置node对象的  next字段
             * 优化点：cmp == next
             * 为什么要先判断？
             * 因为CAS指令  在平台执行时，同一时刻只能有一个 cas指令被执行
             * 有了java层面的这个判断  可以避免一部分cas操作  提升性能
             */
            boolean casNext(SNode cmp, SNode val) {
                return cmp == next &&
                    UNSAFE.compareAndSwapObject(this, nextOffset, cmp, val);
            }

            /**
             * Tries to match node s to this node, if so, waking up thread.
             * Fulfillers call tryMatch to identify their waiters.
             * Waiters block until they have been matched.
             *
             * @param s the node to match
             * @return true if successfully matched to s
             *
             * 尝试匹配
             * 调用tryMatch的对象是  栈顶节点的下一个节点，即与栈顶匹配的节点
             *
             * 匹配成功返回true，匹配失败返回false
             *
             * 匹配模型是：
             * |---------|
             * |         |
             * |         |
             * | REQUEST |
             * | DATA    |
             * |---------|
             */
            boolean tryMatch(SNode s) {
                //条件1成立：表示当前node尚未与任何node发生过匹配
                //条件2成立： 使用CAS设置 match字段成功
                //表示当前 node已经被匹配
                if (match == null &&
                    UNSAFE.compareAndSwapObject(this, matchOffset, null, s)) {
                    //当前node如果自旋结束，那么就会使用 LockSupport.park方法  挂起当前线程   挂起之前将会保存thread到 waiter字段中
                    Thread w = waiter;
                    //条件成立：  表示  node对应的  线程已经被挂起了
                    if (w != null) {    // waiters need at most one unpark
                        waiter = null;
                        LockSupport.unpark(w);
                    }
                    //返回 true表示匹配成功
                    return true;
                }
                //来到这里的几种情况：
                //1、当前node已经和 其他node发生了匹配
                //2、cas设置 match字段失败
                //综上  最后这个条件判断  如果是  设置失败，那么一定会返回false符合期望
                //如果是  发生了匹配  这里会判断两个要匹配的node是否相同  符合期望
                return match == s;
            }

            /**
             * Tries to cancel a wait by matching node to itself.
             * 尝试取消
             * match字段  保留当前node对象本身  表示这个node是取消状态   取消状态的node最终会被强制移除  出栈
             */
            void tryCancel() {
                UNSAFE.compareAndSwapObject(this, matchOffset, null, this);
            }

            /**
             * 如果 match保留的当前 node本身  那表示当前 node是取消状态  反之则是非取消状态
             */
            boolean isCancelled() {
                return match == this;
            }

            // Unsafe mechanics
            private static final sun.misc.Unsafe UNSAFE;
            private static final long matchOffset;
            private static final long nextOffset;

            static {
                try {
                    UNSAFE = sun.misc.Unsafe.getUnsafe();
                    Class<?> k = SNode.class;
                    matchOffset = UNSAFE.objectFieldOffset
                        (k.getDeclaredField("match"));
                    nextOffset = UNSAFE.objectFieldOffset
                        (k.getDeclaredField("next"));
                } catch (Exception e) {
                    throw new Error(e);
                }
            }
        }

        /**
         * The head (top) of the stack
         * 表示栈顶指针
         */
        volatile SNode head;

        /**
         * 设置栈顶元素
         * 优化点：h == head
         * 为什么要先判断？
         * 因为CAS指令  在平台执行时，同一时刻只能有一个 cas指令被执行
         * 有了java层面的这个判断  可以避免一部分cas操作  提升性能
         */
        boolean casHead(SNode h, SNode nh) {
            return h == head &&
                UNSAFE.compareAndSwapObject(this, headOffset, h, nh);
        }

        /**
         * Creates or resets fields of a node. Called only from transfer
         * where the node to push on stack is lazily created and
         * reused when possible to help reduce intervals between reads
         * and CASes of head and to avoid surges of garbage when CASes
         * to push nodes fail due to contention.
         *
         * s   SNode引用  当这个引用为空时 snode方法会创建一个 snode对象 并复制给这个引用
         * o   snode对象的  item字段
         * next   指向当前栈帧的下一个栈帧
         * mode   request / data / full filling
         */
        static SNode snode(SNode s, Object e, SNode next, int mode) {
            if (s == null) s = new SNode(e);
            s.mode = mode;
            s.next = next;
            return s;
        }

        /**
         * Puts or takes an item.
         * 核心方法
         *
         * E   可以为null  为null表示这个请求是一个request请求，不为null表示这个请求是一个data类型的请求
         * timed    是否响应超时，是否值得超时时间   如果为true表示响应超时并且指定超时时间
         * nanos    具体的超时时间限制   单位:纳秒
         *
         * return E  如果当前请求是一个request请求  返回值如果为null表示请求超时或被中断   如果不为null表示匹配成功
         *           如果当前请求是一个data请求  返回值不为null表示请求成功  如果为null  表示请求超时或者被中断
         */
        @SuppressWarnings("unchecked")
        E transfer(E e, boolean timed, long nanos) {
            /*
             * Basic algorithm is to loop trying one of three actions:
             *
             * 1. If apparently empty or already containing nodes of same
             *    mode, try to push node on stack and wait for a match,
             *    returning it, or null if cancelled.
             *
             * 2. If apparently containing node of complementary mode,
             *    try to push a fulfilling node on to stack, match
             *    with corresponding waiting node, pop both from
             *    stack, and return matched item. The matching or
             *    unlinking might not actually be necessary because of
             *    other threads performing action 3:
             *
             * 3. If top of stack already holds another fulfilling node,
             *    help it out by doing its match and/or pop
             *    operations, and then continue. The code for helping
             *    is essentially the same as for fulfilling, except
             *    that it doesn't return the item.
             */

            //包装当前线程的 node
            SNode s = null; // constructed/reused as needed
            //条件成立  表示当前线程是一个 request请求  获取数据
            //否则则表示当前是一个 data请求提交数据
            int mode = (e == null) ? REQUEST : DATA;

            for (;;) {
                //h  表示栈顶指针
                SNode h = head;
                //CASE1: h == null || h.mode == mode
                //条件1成立  表示当前栈为空
                //条件2成立  表示当前栈顶元素与当前元素请求 类型模式相同
                //CASE 成立  表示当前  需要进行入栈操作
                if (h == null || h.mode == mode) {  // empty or same-mode
                    //条件1成立： 表示当前请求  指定了超时限制
                    //条件2成立： nanos<=0  (更多的还是=0的情况)  表示当前请求  不支持 ”阻塞等待“  比如 queue.offer()
                    if (timed && nanos <= 0) {      // can't wait
                        //条件1成立：  表示栈顶元素不是空
                        //条件2成立：  表示栈顶元素已经取消状态了
                        //需要协助栈顶 出栈
                        if (h != null && h.isCancelled())
                            casHead(h, h.next);     // pop cancelled node
                        else
                            //大部分情况都会走到这里
                            return null;
                    } else if (casHead(h, s = snode(s, e, h, mode))) {
                        //来到这里的前置条件：
                        //当前栈为空  或 模式与当前请求一致
                        //并且  当前请求  允许阻塞等待
                        //casHead(h, s = snode(s, e, h, mode))  条件成立
                        //表示 当前请求 入栈成功

                        //入栈成功之后需要做什么事情呢？
                        //其实什么都不需要做  只需要等待  可以匹配的请求过来即可
                        //awaitFulfill  等待被匹配的逻辑   返回的几个情况
                        //1、正常情况  返回匹配的节点
                        //2、取消的情况，返回当前节点   比如s节点进去   s节点出来
                        SNode m = awaitFulfill(s, timed, nanos);

                        //条件成立  表示当前node是取消状态了   需要清理当前 node
                        if (m == s) {               // wait was cancelled
                            //将取消的节点出栈
                            clean(s);
                            //取消状态   最终返回null
                            return null;
                        }

                        //执行到这里  表示当前node  已经被匹配了
                        //如果没有匹配 那就表示当前节点被取消了   如果被取消了的话 会走上面直接return掉

                        //条件1成立： 表示当前栈顶有元素
                        //条件2成立： 表示栈顶的下一个元素是自己
                        //以上条件成立  表示 当前不仅被匹配了  并且两个节点还没有出栈
                        //这个时候  需要帮助出栈
                        if ((h = head) != null && h.next == s)
                            //设置当前head 为两个匹配节点的下一个  协助两个节点出栈
                            casHead(h, s.next);     // help s's fulfiller

                        //假设当前 node模式是  request模式  那么返回和他 匹配节点的 item字段  数据域
                        //如果当前 node模式是  data模式  那么返回当前node item字段
                        return (E) ((mode == REQUEST) ? m.item : s.item);
                    }

                    //CASE2： !isFulfilling(h.mode)
                    //来到这里的前置条件：当前栈顶匀元素不为空   并且 请求模式  不相同
                    //模式不一致的几个情况：
                    //1、  request  data
                    //2、  data  request
                    //3、  full-filling  data/request
                    //以上几个情况  只有 栈顶元素为 full-filling 模式时 无法进行匹配 什么都不需要做
                    //其他 两个情况都需要进行 匹配
                    //!isFulfilling(h.mode)  条件成立  表示 当前栈顶元素不是 full-filling模式
                    //可以进行  元素匹配
                } else if (!isFulfilling(h.mode)) { // try to fulfill
                    //条件成立  表示当前 栈顶元素 处于取消状态
                    //需要协助  栈顶元素出栈
                    if (h.isCancelled())            // already cancelled
                        //协助取消状态节点出栈
                        casHead(h, h.next);         // pop and retry

                    //条件成立： 表示 压栈节点成功  入栈一个 (full-filling | mode) 模式的 node
                    else if (casHead(h, s=snode(s, e, h, FULFILLING|mode))) {

                        //进入这里 表示当前节点已经入栈成功了  可以进行匹配了

                        //自旋匹配  full-filling 节点和  full-filling.next 匹配
                        for (;;) { // loop until matched or waiters disappear
                            //m 与当前 s 匹配节点
                            SNode m = s.next;       // m is s's match

                            //m == null什么时候会成立呢?
                            //当 s.next 节点 超时或者外部线程中断唤醒后  会执行clean操作将自己 清理出栈
                            //这个时候  要和他匹配的线程  就有可能会拿到null
                            if (m == null) {        // all waiters are gone
                                //将整个栈 清空
                                //为什么要将整个栈清空呢？  其实是因为  里面除了自己已经没有元素了
                                //s.next为null的时候  表示  没有其他元素了
                                //所以这个时候 需要把整个栈清空 然后给s重新赋值  重新进行一次自旋 选择路径进行执行
                                casHead(s, null);   // pop fulfill node
                                s = null;           // use new node next time
                                //回到外层大的  自旋中  重新选择路径执行
                                break;              // restart main loop
                            }

                            //执行到这里  表示  s.next节点不为null
                            //这个时候如果有下一个节点  一定是可以和当前节点 匹配的节点  因为不同节点会进行匹配
                            //不会继续留在  栈中

                            //获取匹配节点的下一个节点
                            SNode mn = m.next;

                            //尝试匹配  如果匹配成功  则将这两个节点一起出栈
                            if (m.tryMatch(s)) {
                                //把两个节点一起出队
                                casHead(s, mn);     // pop both s and m
                                //假设当前 node模式是  request模式  那么返回和他 匹配节点的 item字段  数据域
                                //如果当前 node模式是  data模式  那么返回当前node item字段
                                return (E) ((mode == REQUEST) ? m.item : s.item);
                            } else                  // lost match
                                //匹配失败  强制 把当前匹配的节点 出栈
                                //为什么会有这个情况？  其实和上面的 m==null一样  tryMatch匹配成功了 表示当前 m节点已经被修改 match
                                //哪怕后面会有取消操作  那个时候的取消操作也不会生效了
                                //换句话说 极限情况下 tryMatch修改状态成功了  但是线程是自己唤醒的这个时候修改match失败之后
                                //下一次自旋就会正常出队
                                s.casNext(m, mn);   // help unlink
                        }
                    }
                    //CASE3：
                    //来到这里的前置条件：
                    //栈顶 为  full-filling模式 表示栈顶 和栈顶下面的  栈帧正在发生匹配
                    //当前 请求需要 做协助工作
                } else {                            // help a fulfiller
                    //因为有两个节点正在匹配  所以不确定是否可以  具体是要匹配还是要入栈 所以需要协助两个匹配的节点出栈

                    //h这个时候  表示的 full-filling 模式的节点
                    //m 表示  full-filling 匹配的那个节点
                    SNode m = h.next;               // m is h's match

                    //m == null什么时候会成立呢?
                    //当 s.next 节点 超时或者外部线程中断唤醒后  会执行clean操作将自己 清理出栈
                    //这个时候  要和他匹配的线程  就有可能会拿到null
                    if (m == null)                  // waiter is gone
                        //清空当前栈
                        casHead(h, null);           // pop fulfilling node

                    else {
                        //来到这里表示  需要协助出栈了  并且大部分情况都会走到这里

                        //获取栈顶节点 匹配节点的 下一个节点
                        SNode mn = m.next;
                        //尝试匹配  栈顶元素
                        //条件成立 表示 m和栈顶匹配成功
                        if (m.tryMatch(h))          // help match
                            //两个节点一起出栈
                            casHead(h, mn);         // pop both h and m
                        else                        // lost match
                            //强制出栈
                            h.casNext(m, mn);       // help unlink
                    }
                }
            }
        }

        /**
         * Spins/blocks until node s is matched by a fulfill operation.
         *
         * @param s the waiting node
         * @param timed true if timed wait
         * @param nanos timeout value
         * @return matched node, or s if cancelled
         *
         * s   表示当前请求的node
         * timed  当前请求是否支持超时限制
         * nanos  如果请求支持超时限制 表示超时时长
         */
        SNode awaitFulfill(SNode s, boolean timed, long nanos) {
            /*
             * When a node/thread is about to block, it sets its waiter
             * field and then rechecks state at least one more time
             * before actually parking, thus covering race vs
             * fulfiller noticing that waiter is non-null so should be
             * woken.
             *
             * When invoked by nodes that appear at the point of call
             * to be at the head of the stack, calls to park are
             * preceded by spins to avoid blocking when producers and
             * consumers are arriving very close in time.  This can
             * happen enough to bother only on multiprocessors.
             *
             * The order of checks for returning out of main loop
             * reflects fact that interrupts have precedence over
             * normal returns, which have precedence over
             * timeouts. (So, on timeout, one last check for match is
             * done before giving up.) Except that calls from untimed
             * SynchronousQueue.{poll/offer} don't check interrupts
             * and don't wait at all, so are trapped in transfer
             * method rather than calling awaitFulfill.
             */

            //如果指定了超时限制   deadline  表示等待的截至时间
            final long deadline = timed ? System.nanoTime() + nanos : 0L;
            //获取当前请求线程
            Thread w = Thread.currentThread();

            //spins 表示当前请求线程 在下面的自旋检查中的  自旋次数
            //如果 spins 达到最大自旋次数时  当前线程对应的 node 仍然没有被匹配成功  那么再选择挂起当前请求的线程
            int spins = (shouldSpin(s) ?
                    // timed = true  表示指定了超时限制的 这个时候使用 maxUntimedSpins=32  否则使用  32*16
                         (timed ? maxTimedSpins : maxUntimedSpins) : 0);

            //自旋检查逻辑
            //1、检查是否匹配
            //2、检查是否超时
            //3、检查是否中断
            for (;;) {
                //条件成立  表示当前线程收到中断信号  需要设置node状态为取消状态
                if (w.isInterrupted())
                    //设置 node对象的 match指向自己  表示该node状态为 取消状态
                    s.tryCancel();

                //获取当前 节点的  匹配节点
                //match  有值的几种情况：
                //1、正常情况： 有一个请求与  当前node节点匹配成功 这个时候 match 指向匹配节点
                //2、取消状态： 当前match  指向  当前node
                SNode m = s.match;
                //条件成立  表示match  指针有值了  这个时候可能时正常的  也可能时被取消了
                if (m != null)
                    //直接返回  match节点
                    return m;

                //条件成立： 表示指定了超时限制
                if (timed) {
                    //获取剩余  等待时间(距离超时还有多少 纳秒)
                    nanos = deadline - System.nanoTime();
                    //条件成立： 表示已经超时了
                    if (nanos <= 0L) {
                        //设置当前 node状态为 取消状态  (match指向当前node)
                        s.tryCancel();
                        //继续自旋判断
                        continue;
                    }
                }

                //条件成立   表示当前当前线程还可以进行自旋检查
                if (spins > 0)
                    //条件成立  shouldSpin(s)  表示可以自旋检查   自旋次数-1
                    //条件不成   表示不能自旋检查了
                    spins = shouldSpin(s) ? (spins-1) : 0;

                //前置条件：  spins==0  表示已经不允许自旋检查了
                //条件成立   表示 当前节点的  waiter字段为 null
                else if (s.waiter == null)
                    //需要设置  当前线程到  waiter字段中
                    s.waiter = w; // establish waiter so can park next iter


                //前置条件： 当前线程 不允许检查了 并且已经设置了  waiter字段
                //条件成立 ：  说明当前线程未指定超时限制
                else if (!timed)
                    //可以使用   不指定超时时长的park方法 挂起当前线程  直到外部线程使用 unpark唤醒
                    LockSupport.park(this);

                //前置条件：  当前线程 不允许检查了 并且已经设置了  waiter字段   并且当前线程指定了超时限制
                //条件成立：  表示剩余等待时间   > 1000纳秒  只有这个情况才允许 挂起当前线程
                //如果低于 这个时候  挂起唤醒的成本  远大于  自旋 
                else if (nanos > spinForTimeoutThreshold)
                    LockSupport.parkNanos(this, nanos);
            }
        }

        /**
         * Returns true if node s is at head or there is an active
         * fulfiller.
         * 判断当前节点是否允许自旋检查
         */
        boolean shouldSpin(SNode s) {
            //获取当前栈顶元素
            SNode h = head;
            //条件1成立：  表示当前元素就是栈顶元素   允许自旋检查
            //条件2成立：  表示栈顶元素为null
            //条件成立的情况：   当前s节点 自旋检查期间  又来了一个 与当前s节点 匹配的请求  一起出栈了  条件会成立
            //条件3成立： 表示栈顶元素 模式为  full-filling模式 正在匹配  (前置条件：当前元素不是栈顶元素)
            //这个情况下  栈顶下面的元素  都允许自旋检查
            return (h == s || h == null || isFulfilling(h.mode));
        }

        /**
         * Unlinks s from the stack.
         * 清空当前元素  传入的s一定是   取消的节点
         */
        void clean(SNode s) {
            //直接清空 s节点的数据域  以及等待线程引用
            s.item = null;   // forget item
            s.waiter = null; // forget thread

            /*
             * At worst we may need to traverse entire stack to unlink
             * s. If there are multiple concurrent calls to clean, we
             * might not see s if another thread has already removed
             * it. But we can stop when we see any node known to
             * follow s. We use s.next unless it too is cancelled, in
             * which case we try the node one past. We don't check any
             * further because we don't want to doubly traverse just to
             * find sentinel.
             */

            //检查取消节点的截至位置  清理的时候把遇到的取消状态的节点一起清理出去
            //past 不一定是一个  取消状态的节点  也有可能是一个正常状态的节点
            SNode past = s.next;

            //继续往下判断 如果紧接着的这个 也是取消状态  那么past位置为  下面这个
            if (past != null && past.isCancelled())
                past = past.next;

            // Absorb cancelled nodes at head
            //当前循环检查节点
            SNode p;
            //从栈顶开始向下检查 将栈顶以下  取消状态的节点全部清理出去  知道遇到 past为止
            while ((p = head) != null && p != past && p.isCancelled())
                casHead(p, p.next);

            // Unsplice embedded nodes
            //条件成立  表示  上一个循环检查的过程中有一个  正常的节点中断了流程
            //所以这个条件会成立
            //需要  从这个p开始 再次向下  清理取消状态的节点  知道遇到 past为止
            while (p != null && p != past) {
                //获取当前循环节点 的下一个节点
                SNode n = p.next;
                //条件成立  表示当前节点的下一个节点 是一个取消状态的节点
                if (n != null && n.isCancelled())
                    //把当前节点的下一个节点  出栈
                    p.casNext(n, n.next);
                else
                    //条件成立  当前节点不是取消状态的节点
                    //设置当前节点为下一个节点继续遍历
                    p = n;
            }
        }

        // Unsafe mechanics
        private static final sun.misc.Unsafe UNSAFE;
        private static final long headOffset;
        static {
            try {
                UNSAFE = sun.misc.Unsafe.getUnsafe();
                Class<?> k = TransferStack.class;
                headOffset = UNSAFE.objectFieldOffset
                    (k.getDeclaredField("head"));
            } catch (Exception e) {
                throw new Error(e);
            }
        }
    }

    /**
     * Dual Queue
     * 公平模式的  同步队列
     */
    static final class TransferQueue<E> extends Transferer<E> {
        /*
         * This extends Scherer-Scott dual queue algorithm, differing,
         * among other ways, by using modes within nodes rather than
         * marked pointers. The algorithm is a little simpler than
         * that for stacks because fulfillers do not need explicit
         * nodes, and matching is done by CAS'ing QNode.item field
         * from non-null to null (for put) or vice versa (for take).
         */

        /** Node class for TransferQueue. */
        static final class QNode {
            //指向  当前节点的  下一个节点  指针
            volatile QNode next;          // next node in queue
            //数据域  如果当前节点是  data类型的请求  这里表示数据域  如果是  request类型的请求  item=null
            volatile Object item;         // CAS'ed to or from null
            //当node 对应的线程未匹配到节点的时候  对应的线程会挂起  并且把当前线程的引用保存到这里
            volatile Thread waiter;       // to control park/unpark
            //true  表示当前 node是一个 data类型的请求   false表示当前node是一个  request类型的请求
            final boolean isData;

            QNode(Object item, boolean isData) {
                this.item = item;
                this.isData = isData;
            }

            /**
             * CAS修改当前节点的 next引用
             */
            boolean casNext(QNode cmp, QNode val) {
                return next == cmp &&
                    UNSAFE.compareAndSwapObject(this, nextOffset, cmp, val);
            }

            /**
             * CAS修改 当前节点的数据域 item
             */
            boolean casItem(Object cmp, Object val) {
                return item == cmp &&
                    UNSAFE.compareAndSwapObject(this, itemOffset, cmp, val);
            }

            /**
             * Tries to cancel by CAS'ing ref to this as item.
             * 尝试取消当前节点   item=自己  表示节点被取消
             */
            void tryCancel(Object cmp) {
                UNSAFE.compareAndSwapObject(this, itemOffset, cmp, this);
            }

            /**
             * 判断当前节点是否被取消
             */
            boolean isCancelled() {
                return item == this;
            }

            /**
             * Returns true if this node is known to be off the queue
             * because its next pointer has been forgotten due to
             * an advanceHead operation.
             * 判断当前节点是否   “不在”队列中
             * 当 next指向自己  表示当前节点已经出队
             */
            boolean isOffList() {
                return next == this;
            }

            // Unsafe mechanics
            private static final sun.misc.Unsafe UNSAFE;
            private static final long itemOffset;
            private static final long nextOffset;

            static {
                try {
                    UNSAFE = sun.misc.Unsafe.getUnsafe();
                    Class<?> k = QNode.class;
                    itemOffset = UNSAFE.objectFieldOffset
                        (k.getDeclaredField("item"));
                    nextOffset = UNSAFE.objectFieldOffset
                        (k.getDeclaredField("next"));
                } catch (Exception e) {
                    throw new Error(e);
                }
            }
        }

        /**
         * Head of queue
         * 指向队列的 dummy节点
         * 真正的头节点其实是  head.next   原理同AQS相似
         * 第一个节点是 dummy节点  这个节点其实是一个虚假节点  要么是没有封装对象的要么是已经出队的  要么就什么都不是
         * 相当于只是  一个用来  代理充当头的一个节点    就比如舞狮的那个狮子头  只是当作一个头  没有其他作用
         */
        transient volatile QNode head;

        /**
         * Tail of queue
         * 指向队列 尾巴的节点
         */
        transient volatile QNode tail;
        /**
         * Reference to a cancelled node that might not yet have been
         * unlinked from queue because it was the last inserted node
         * when it was cancelled.
         * 表示被清理节点 的 前驱节点
         * 因为入队操作是分两步完成的：
         * 1、设置tail.next = 自己
         * 2、CAS  tail = 自己
         * 如果队尾节点要清理出队的话   就变成了一种特殊的出队情况
         * 这个时候就需要保存  当前tail节点的前一个节点   然后再进行出队
         */
        transient volatile QNode cleanMe;

        TransferQueue() {
            //创建一个  dummy节点  设置为头节点  在整个队列初始化的时候
            QNode h = new QNode(null, false); // initialize to dummy node.
            head = h;
            tail = h;
        }

        /**
         * Tries to cas nh as new head; if successful, unlink
         * old head's next node to avoid garbage retention.
         * 设置 头指针指向新的节点  也就相当于把老的头节点出队
         */
        void advanceHead(QNode h, QNode nh) {
            //条件成立   表示设置头节点为  nh成功
            if (h == head &&
                UNSAFE.compareAndSwapObject(this, headOffset, h, nh))
                //这个时候 把头结点的  next指向自己  表示自己已经是一个  出队的节点了
                h.next = h; // forget old next
        }

        /**
         * Tries to cas nt as new tail.
         * 更新队尾节点为  新的  队尾节点
         * t表示 老的队尾
         * nt表示  新的队尾
         */
        void advanceTail(QNode t, QNode nt) {
            if (tail == t)
                UNSAFE.compareAndSwapObject(this, tailOffset, t, nt);
        }

        /**
         * Tries to CAS cleanMe slot.
         * 更新 cleanMe 为新的 cleanMe
         */
        boolean casCleanMe(QNode cmp, QNode val) {
            return cleanMe == cmp &&
                UNSAFE.compareAndSwapObject(this, cleanMeOffset, cmp, val);
        }

        /**
         * Puts or takes an item.
         */
        @SuppressWarnings("unchecked")
        E transfer(E e, boolean timed, long nanos) {
            /* Basic algorithm is to loop trying to take either of
             * two actions:
             *
             * 1. If queue apparently empty or holding same-mode nodes,
             *    try to add node to queue of waiters, wait to be
             *    fulfilled (or cancelled) and return matching item.
             *
             * 2. If queue apparently contains waiting items, and this
             *    call is of complementary mode, try to fulfill by CAS'ing
             *    item field of waiting node and dequeuing it, and then
             *    returning matching item.
             *
             * In each case, along the way, check for and try to help
             * advance head and tail on behalf of other stalled/slow
             * threads.
             *
             * The loop starts off with a null check guarding against
             * seeing uninitialized head or tail values. This never
             * happens in current SynchronousQueue, but could if
             * callers held non-volatile/final ref to the
             * transferer. The check is here anyway because it places
             * null checks at top of loop, which is usually faster
             * than having them implicitly interspersed.
             */

            //s 指向当前请求对应的node
            QNode s = null; // constructed/reused as needed
            //isData = true  表示当前请求是一个 写数据的操作
            //否则 表示当前请求是一个  获取数据的操作
            boolean isData = (e != null);

            //自旋
            for (;;) {
                //获取头节点   尾节点
                QNode t = tail;
                QNode h = head;

                //头节点和  尾节点存在任意一个为空  这个时候继续自旋   几乎没有可能会来到这里
                if (t == null || h == null)         // saw uninitialized value
                    continue;                       // spin

                //条件1成立：  表示队列刚刚初始化   tail = head  两个指针都指向虚假节点
                //当前节点是第一个节点  需要进行入队操作
                //条件2成立：   表示  队尾的 请求类型与  当前请求类型相同   无法进行匹配
                //所以这个时候节点也需要入队操作
                if (h == t || t.isData == isData) { // empty or same-mode
                    //获取  tail节点的下一个节点
                    QNode tn = t.next;

                    //判断 tail节点是否发生了变化  如果发生了变化 就需要重新自旋判断  是需要入队还是匹配操作了
                    //因为是多线程的情况  可能有其他线程已经捷足先登了
                    if (t != tail)                  // inconsistent read
                        //回到自旋再次选择路径执行
                        continue;

                    //条件成立  表示已经有一个节点  设置到tail.next里面了
                    //但是 可能 还没有把 tail设置进去
                    if (tn != null) {               // lagging tail
                        //协助 已经入队的节点  设置tail 指针
                        //协助完成之后  回到自旋再次选择路径执行
                        advanceTail(t, tn);
                        continue;
                    }

                    //条件成立  表示当前 线程是支持超时等待的  但是不支持阻塞等待  可能是从 offer()这种方法进来的
                    //但是当前是  公平队列  所以直接拒绝了
                    //换个方式理解就是：  你支持超时等待  但是你没有等待时间了
                    //你如果不能直接匹配，那么就直接返回了  因为没有时间了
                    if (timed && nanos <= 0)        // can't wait
                        //返回 null
                        return null;

                    //如果s 为null表示  还没有进行初始化这个时候进行初始化
                    if (s == null)
                        //创建新节点并初始化  赋值给s
                        s = new QNode(e, isData);

                    //尝试设置  当前节点为   tail的尾节点  这里也证明了  只要这个时候设置成功
                    //就表示当前节点已经入队成功了  其他节点只能从自己这个节点开始   所以需要协助自己变成tail
                    if (!t.casNext(null, s))        // failed to link in
                        //来到这里表示  CAS竞争失败了   需要重新自旋
                        continue;

                    //更新当前节点为 tail节点  这里其实不会失败
                    //其他线程成功了  也就相当于协助  当前节点 变成队尾了
                    advanceTail(t, s);              // swing tail and wait

                    //1、当前请求为 data模式时：
                    //1.2  x == this 当前 s node对应的线程  为取消状态
                    //1.3  x == null 表示已经有匹配的节点了  并且匹配节点已经拿走了数据
                    //2、当前请求未  request模式时：
                    //2.2  x == this 当前 s node对应的线程  为取消状态
                    //2.3  (x != null  && x!= this) 表示当前request已经匹配到一个 data类型的node了，  并且获取到其中的数据域了
                    Object x = awaitFulfill(s, e, timed, nanos);

                    //条件成立  表示当前 node的状态是  取消状态   需要做清理出队逻辑
                    if (x == s) {                   // wait was cancelled
                        //在这里 t表示s的前驱节点  s表示当前被唤醒的节点
                        clean(t, s);
                        return null;
                    }

                    //执行到这里表示  当前node是匹配成功
                    //1、当前线程在 awaitFulfill方法中被挂起了  执行到这里  是被匹配节点使用 LockSupport.unpark方法唤醒的
                    //被唤醒之后 唤醒它的线程  已经帮他出队了  所以  s.isOffList()方法成立
                    //2、当前线程在 awaitFulfill方法中  没有被挂起  而是自己自旋检查的时候  发现已经匹配了 从而 返回到上层的
                    //这个时候  当前节点就不一定出队了  s.isOffList()就会有可能会成立  如果成立  就需要自己把自己出队处理

                    //条件成立  说明当前node仍然在 队列内  需要做  匹配成功后的出队逻辑
                    if (!s.isOffList()) {           // not already unlinked
                        //t为  当前s节点的前驱节点   更新dummy节点为s节点   表示head.next节点已经出队了(因为 head节点是一个假节点)

                        //为什么是 这样的?   明明t是 尾节点的引用  却当作头节点的引用来使用?
                        //首先，我们知道唤醒的顺序是从 head.next节点开始唤醒的   入队的大概图如下
                        // head(dummy节点)  ->   第一个入队的S节点   ->  第二个入队的X节点   ->  第三个入队的Y节点
                        //这个时候  第一个节点(S)的 t是一个 dummy节点  是一个虚假节点所以可以直接使用t
                        //第二个进来的节点(X)，  t就变成了 head.next节点 也就是节点S  这个时候，  X节点要想被唤醒
                        //那么就只能  等S节点  唤醒或取消之后才可以   而S节点取消或  唤醒之后  队列变成了下面的样子
                        //head(第一个入队的S节点  dummy节点)   ->  第二个入队的X节点   ->  第三个入队的Y节点
                        //这个时候  X保存的 t节点刚好变成了  head节点  所以这里的  t其实时时刻刻表示的是  当前节点的前一个节点
                        //而自己被唤醒之后   前一个节点一定会变成  head节点  所以可以这样使用

                        advanceHead(t, s);          // unlink if head

                        //条件成立表示  当前s节点为 request模式  并且已经获取到匹配的数据了
                        //因为  s节点已经出队了  这个时候需要设置item为自己  表示他是一个取消、要出队的一个状态
                        if (x != null)              // and forget fields
                            s.item = s;

                        //清空 等待者线程
                        s.waiter = null;
                    }

                    //基于以上条件  来到这里只要根据实际情况返回即可
                    //如果是  data返回传入的e
                    //如果是  request  返回获取到的x
                    return (x != null) ? (E)x : e;

                    //来到这里的几种情况：
                    //队尾节点与当前节点互补  (为什么这种情况可以进来，因为可以匹配的早都匹配了  如果不是一个队列 清一色是压根不会有数据被匹配)
                    //这个时候  就要从 队头开始尝试进行匹配了
                } else {                            // complementary-mode
                    //获取 头节点的 next节点  也就是真正的头节点  可以被匹配的那个
                    //因为当前是一个  公平模式的同步队列  所以需要从头节点开始
                    QNode m = h.next;               // node to fulfill

                    //条件1成立：  表示tail节点已经发生变化了，其他线程已经并发修改了tail节点，当前线程看到的是一个过期数据，需要重新自旋
                    //条件2成立：  表示  head.next节点  已经被别人匹配走了， 这个时候 当前线程看到的也是一个过期数据， 依然需要重新自旋
                    //条件3成立：  表示 head节点 也已经发生变化了  已经有线程匹配了head.next节点 并且修改了head节点  又是一个过期数据的情况
                    if (t != tail || m == null || h != head)
                        continue;                   // inconsistent read

                    //执行到这里 表示  t  m  h  目前来看是准确数据

                    //获取当前要匹配节点的  数据域 item
                    Object x = m.item;

                    //条件1:  isData是表示当前  节点 data模式还是  request模式
                    //假设 isData = true   m就是request模式的节点  x就是request的数据域因为还没有匹配  x=null
                    //那么   true == ( null !=null)   -> true == false   ->  false
                    //假设 isDate = false  m就是data模式的节点   x就是data的数据域  x!=null的
                    //那么  false == ( x !=null )  ->  false == true   ->  false
                    //综上  也就是正常情况下  条件1不成立

                    //条件2成立：  表示当前节点已经过期了   m节点已经是取消状态了  不能进行匹配了  需要continue  重新选择路径执行

                    //条件3   前置条件：  m节点不是取消状态的节点
                    //假设当前请求是 request模式   那么m就是data模式  m.casItem(x, e)  表示把m的item清空  也就是相当于拿走了 m节点的数据
                    //假设当前请求是 data模式  那么m就是request模式  m.casItem(x, e)  表示把m的item设置数据进去  相当于把数据塞给了 m节点
                    if (isData == (x != null) ||    // m already fulfilled
                        x == m ||                   // m cancelled
                        !m.casItem(x, e)) {         // lost CAS
                        //进入到这里
                        advanceHead(h, m);          // dequeue and retry
                        continue;
                    }

                    //执行到这里  说明 匹配已经完成了  也就是双方的item域已经处理过了   这个时候需要做以下事情：
                    //1、给真正的头节点出队
                    //2、唤醒匹配节点的线程
                    //3、返回应该返回的值

                    //节点出队
                    advanceHead(h, m);              // successfully fulfilled

                    //唤醒m线程
                    LockSupport.unpark(m.waiter);

                    //如果是  data返回传入的e
                    //如果是  request  返回获取到的x
                    return (x != null) ? (E)x : e;
                }
            }
        }

        /**
         * Spins/blocks until node s is fulfilled.
         *
         * @param s the waiting node
         * @param e the comparison value for checking match
         * @param timed true if timed wait
         * @param nanos timeout value
         * @return matched item, or s if cancelled
         */
        Object awaitFulfill(QNode s, E e, boolean timed, long nanos) {
            /* Same idea as TransferStack.awaitFulfill */

            //获取当前  线程等待的截至时间  单位纳秒
            final long deadline = timed ? System.nanoTime() + nanos : 0L;
            //获取当前  请求节点的   线程
            Thread w = Thread.currentThread();

            //和非公平模式一样  表示自旋检查的次数
            //并且有且只有  head.next节点允许  自旋检查 其他节点只能挂起
            int spins = ((head.next == s) ?
                         (timed ? maxTimedSpins : maxUntimedSpins) : 0);

            //自旋检查：
            //1、检查状态等待匹配
            //2、挂起当前线程
            //3、检查当前线程是否被中断  或超时
            for (;;) {

                //条件成立 表示线程等待过程中  收到了中断信号  属于中断唤醒
                if (w.isInterrupted())
                    //更新线程对应的node状态为  取消状态
                    //数据域 item指向了自己  表示取消状态
                    s.tryCancel(e);

                //获取当前节点的数据域

                //数据域的几种情况：

                //1、当 s node为Data模式时   e表示 请求带来的数据
                //1.1  (item != null && item != this) 表示请求要传递的数据
                //1.2  item == this 当前 s node对应的线程  为取消状态
                //1.3  item == null 表示已经有匹配的节点了  并且匹配节点已经拿走了数据

                //2、当 s node为request模式时  e=null
                //2.1  item == null  表示当前请求 仍然未匹配到对应的DATA请求
                //2.2  item == this 当前 s node对应的线程  为取消状态
                //2.3  (item != null  && item != this) 表示当前request已经匹配到一个 data类型的node了，  并且获取到其中的数据域了
                Object x = s.item;

                //条件成立的几种情况：
                //1、当前请求为 data模式时：
                //1.2  item == this 当前 s node对应的线程  为取消状态
                //1.3  item == null 表示已经有匹配的节点了  并且匹配节点已经拿走了数据

                //2、当前请求未  request模式时：
                //2.2  item == this 当前 s node对应的线程  为取消状态
                //2.3  (item != null  && item != this) 表示当前request已经匹配到一个 data类型的node了，  并且获取到其中的数据域了
                if (x != e)
                    return x;

                //条件成立：  表示当前请求的线程  指定了超时限制
                if (timed) {
                    //获取  剩余超时时间
                    nanos = deadline - System.nanoTime();
                    //条件成立  表示   当前线程已经等待超时了
                    if (nanos <= 0L) {
                        //尝试取消当前节点   并跳出自旋
                        //如果取消失败  可能是被其他线程匹配了
                        s.tryCancel(e);
                        continue;
                    }
                }

                //条件成立表示   当前线程还可以自旋检查
                if (spins > 0)
                    --spins;

                //条件成立  表示 线程已经无法进行自旋检查了  这个时候 waiter线程还没设置当前线程
                else if (s.waiter == null)
                    //保存 node对应的线程  方便挂起之后  后面其他线程唤醒自己
                    s.waiter = w;
                //条件成立   表示线程 没有指定超时限制  可以直接挂起
                else if (!timed)
                    LockSupport.park(this);
                //条件成立   表示当前  线程指定了  超时限制  并且  剩余等待时间大于最小超时限制
                //这个情况下  才允许  超时挂起
                else if (nanos > spinForTimeoutThreshold)
                    LockSupport.parkNanos(this, nanos);
            }
        }

        /**
         * Gets rid of cancelled node s with original predecessor pred.
         */
        void clean(QNode pred, QNode s) {
            //清空s节点的  线程引用
            s.waiter = null; // forget thread
            /*
             * At any given time, exactly one node on list cannot be
             * deleted -- the last inserted node. To accommodate this,
             * if we cannot delete s, we save its predecessor as
             * "cleanMe", deleting the previously saved version
             * first. At least one of node s or the node previously
             * saved can always be deleted, so this always terminates.
             */
            //条件成立  表示  pred节点下一个节点是 s   也就是当前pred节点并没有被取消   pred节点还是有效的
            while (pred.next == s) { // Return early if already unlinked
                //获取当前头节点
                QNode h = head;
                //获取头节点的  next节点
                QNode hn = h.next;   // Absorb cancelled first node as head

                //条件成立 表示 head.next节点  存在  并且已经被取消
                if (hn != null && hn.isCancelled()) {
                    //设置 head(dummy)节点  把被取消的  head.next节点出队  因为拿到了过期数据所以需要重新自旋
                    advanceHead(h, hn);
                    continue;
                }

                //获取当前尾节点
                QNode t = tail;      // Ensure consistent read for tail
                //条件成立  表示当前队列中  已经没有有效的节点了  直接返回即可
                if (t == h)
                    return;

                //获取  尾节点的next节点
                QNode tn = t.next;
                //条件成立  表示  尾节点已经被更改   有新的节点入队   获取到的尾节点已经发生变化   需要重新自旋
                if (t != tail)
                    continue;

                //条件成立  表示  tail节点还有next节点  也就是当前有了新的节点入队  需要帮助修正tail节点  并重新自旋
                if (tn != null) {
                    advanceTail(t, tn);
                    continue;
                }


                //条件成立：   表示当前节点不是  tail节点
                if (s != t) {        // If not tail, try to unsplice
                    //获取当前节点的next节点
                    QNode sn = s.next;
                    //条件1成立  表示当前节点已经出队
                    //条件2成立  表示修改前驱节点的next节点成功  顺便帮助了 当前节点出队
                    if (sn == s || pred.casNext(s, sn))
                        return;
                }



                //来到这里表示  当前节点已经是tail节点了(是当前视角下的tail节点)

                //获取当前cleanMe的引用
                QNode dp = cleanMe;

                //条件成立   表示当前cleanMe已经被赋值
                //条件不成立  表示当前cleanMe没有被 赋值  需要初始化赋值
                if (dp != null) {    // Try unlinking previous cancelled node
                    //进入这里表示  肯定有一个节点需要被清理   因为第一个需要被清理的节点只是修改 cleanMe的标记没有做实际出队处理
                    //并且  cleanMe标记着   下一个节点是需要被清理的节点

                    //获取  cleanMe的  next节点
                    QNode d = dp.next;
                    QNode dn;

                    //条件1：   d == null
                    //条件成立   表示 clearMe的next节点已经为空了  说明什么？说明有线程已经修改过clearMe了,下一个节点已经被清理过了
                    //条件2：   d == dp
                    //条件成立   表示 当前cleanMe  标记的这个节点已经出队了     一般情况下也不成立
                    //条件3：   !d.isCancelled()
                    //条件成立    表示  d节点不是取消状态的节点   也就是cleanMe后面紧接着的那个节点   不是取消状态
                    //(成立的时候一般是  这个节点已经被别人处理了)   一般情况下也不成立

                    //上面几个只要有一个是true就  会进入清空cleanMe的逻辑   以上条件有一个成立都表示这个cleanMe已经被处理过了
                    //那么后面的条件  就有可能需要处理  cleanMe后面的节点

                    //条件4：   (d != t &&  (dn = d.next) != null &&  dn != d &&   dp.casNext(d, dn))
                    //4.1   t表示当前线程标记的尾节点   d=t  表示d已经是尾节点了  这个时候就不需要处理了
                    //所以  d!=t  成立  表示当前节点可能还需要处理
                    //4.2   (dn = d.next) != null  条件成立   也就是被取消节点后面还有一个入队的节点(清理出队的前提条件)
                    //4.3   dn != d     条件成立  表示后续节点还在队列中
                    //4.4   dp.casNext(d, dn)   条件成立  表示修改 cleanMe的next节点为  下下个节点成功(在这里把  cleanMe后面的取消节点出队)
                    //条件4成立  表示cleanMe的节点需要被  清理  并且 cleanMe的节点已经被修改出队了
                    //因为队列是从  head开始遍历的  只要修改了  next指针  就无法获取到被跳过的节点
                    if (d == null ||               // d is gone or
                        d == dp ||                 // d is off list or
                        !d.isCancelled() ||        // d not cancelled or
                        (d != t &&                 // d not tail and
                         (dn = d.next) != null &&  //   has successor
                         dn != d &&                //   that is on list
                         dp.casNext(d, dn)))       // d unspliced
                        //清空cleanMe节点
                        casCleanMe(dp, null);

                    //条件成立：  表示标记的cleanMe节点和  前驱节点一致
                    //
                    if (dp == pred)
                        return;      // s is already saved node

                    //前置条件：   cleanMe节点为null
                    //条件成立：   表示修改 cleanMe成功
                    //修改成功之后，本次  clean操作结束，等待下一个需要clean的线程清理
                } else if (casCleanMe(null, pred))
                    return;          // Postpone cleaning s
            }
        }

        private static final sun.misc.Unsafe UNSAFE;
        private static final long headOffset;
        private static final long tailOffset;
        private static final long cleanMeOffset;
        static {
            try {
                UNSAFE = sun.misc.Unsafe.getUnsafe();
                Class<?> k = TransferQueue.class;
                headOffset = UNSAFE.objectFieldOffset
                    (k.getDeclaredField("head"));
                tailOffset = UNSAFE.objectFieldOffset
                    (k.getDeclaredField("tail"));
                cleanMeOffset = UNSAFE.objectFieldOffset
                    (k.getDeclaredField("cleanMe"));
            } catch (Exception e) {
                throw new Error(e);
            }
        }
    }

    /**
     * The transferer. Set only in constructor, but cannot be declared
     * as final without further complicating serialization.  Since
     * this is accessed only at most once per public method, there
     * isn't a noticeable performance penalty for using volatile
     * instead of final here.
     */
    private transient volatile Transferer<E> transferer;

    /**
     * Creates a {@code SynchronousQueue} with nonfair access policy.
     */
    public SynchronousQueue() {
        this(false);
    }

    /**
     * Creates a {@code SynchronousQueue} with the specified fairness policy.
     *
     * @param fair if true, waiting threads contend in FIFO order for
     *        access; otherwise the order is unspecified.
     */
    public SynchronousQueue(boolean fair) {
        transferer = fair ? new TransferQueue<E>() : new TransferStack<E>();
    }

    /**
     * Adds the specified element to this queue, waiting if necessary for
     * another thread to receive it.
     *
     * @throws InterruptedException {@inheritDoc}
     * @throws NullPointerException {@inheritDoc}
     */
    public void put(E e) throws InterruptedException {
        if (e == null) throw new NullPointerException();
        if (transferer.transfer(e, false, 0) == null) {
            Thread.interrupted();
            throw new InterruptedException();
        }
    }

    /**
     * Inserts the specified element into this queue, waiting if necessary
     * up to the specified wait time for another thread to receive it.
     *
     * @return {@code true} if successful, or {@code false} if the
     *         specified waiting time elapses before a consumer appears
     * @throws InterruptedException {@inheritDoc}
     * @throws NullPointerException {@inheritDoc}
     */
    public boolean offer(E e, long timeout, TimeUnit unit)
        throws InterruptedException {
        if (e == null) throw new NullPointerException();
        if (transferer.transfer(e, true, unit.toNanos(timeout)) != null)
            return true;
        if (!Thread.interrupted())
            return false;
        throw new InterruptedException();
    }

    /**
     * Inserts the specified element into this queue, if another thread is
     * waiting to receive it.
     *
     * @param e the element to add
     * @return {@code true} if the element was added to this queue, else
     *         {@code false}
     * @throws NullPointerException if the specified element is null
     */
    public boolean offer(E e) {
        if (e == null) throw new NullPointerException();
        return transferer.transfer(e, true, 0) != null;
    }

    /**
     * Retrieves and removes the head of this queue, waiting if necessary
     * for another thread to insert it.
     *
     * @return the head of this queue
     * @throws InterruptedException {@inheritDoc}
     */
    public E take() throws InterruptedException {
        E e = transferer.transfer(null, false, 0);
        if (e != null)
            return e;
        Thread.interrupted();
        throw new InterruptedException();
    }

    /**
     * Retrieves and removes the head of this queue, waiting
     * if necessary up to the specified wait time, for another thread
     * to insert it.
     *
     * @return the head of this queue, or {@code null} if the
     *         specified waiting time elapses before an element is present
     * @throws InterruptedException {@inheritDoc}
     */
    public E poll(long timeout, TimeUnit unit) throws InterruptedException {
        E e = transferer.transfer(null, true, unit.toNanos(timeout));
        if (e != null || !Thread.interrupted())
            return e;
        throw new InterruptedException();
    }

    /**
     * Retrieves and removes the head of this queue, if another thread
     * is currently making an element available.
     *
     * @return the head of this queue, or {@code null} if no
     *         element is available
     */
    public E poll() {
        return transferer.transfer(null, true, 0);
    }

    /**
     * Always returns {@code true}.
     * A {@code SynchronousQueue} has no internal capacity.
     *
     * @return {@code true}
     */
    public boolean isEmpty() {
        return true;
    }

    /**
     * Always returns zero.
     * A {@code SynchronousQueue} has no internal capacity.
     *
     * @return zero
     */
    public int size() {
        return 0;
    }

    /**
     * Always returns zero.
     * A {@code SynchronousQueue} has no internal capacity.
     *
     * @return zero
     */
    public int remainingCapacity() {
        return 0;
    }

    /**
     * Does nothing.
     * A {@code SynchronousQueue} has no internal capacity.
     */
    public void clear() {
    }

    /**
     * Always returns {@code false}.
     * A {@code SynchronousQueue} has no internal capacity.
     *
     * @param o the element
     * @return {@code false}
     */
    public boolean contains(Object o) {
        return false;
    }

    /**
     * Always returns {@code false}.
     * A {@code SynchronousQueue} has no internal capacity.
     *
     * @param o the element to remove
     * @return {@code false}
     */
    public boolean remove(Object o) {
        return false;
    }

    /**
     * Returns {@code false} unless the given collection is empty.
     * A {@code SynchronousQueue} has no internal capacity.
     *
     * @param c the collection
     * @return {@code false} unless given collection is empty
     */
    public boolean containsAll(Collection<?> c) {
        return c.isEmpty();
    }

    /**
     * Always returns {@code false}.
     * A {@code SynchronousQueue} has no internal capacity.
     *
     * @param c the collection
     * @return {@code false}
     */
    public boolean removeAll(Collection<?> c) {
        return false;
    }

    /**
     * Always returns {@code false}.
     * A {@code SynchronousQueue} has no internal capacity.
     *
     * @param c the collection
     * @return {@code false}
     */
    public boolean retainAll(Collection<?> c) {
        return false;
    }

    /**
     * Always returns {@code null}.
     * A {@code SynchronousQueue} does not return elements
     * unless actively waited on.
     *
     * @return {@code null}
     */
    public E peek() {
        return null;
    }

    /**
     * Returns an empty iterator in which {@code hasNext} always returns
     * {@code false}.
     *
     * @return an empty iterator
     */
    public Iterator<E> iterator() {
        return Collections.emptyIterator();
    }

    /**
     * Returns an empty spliterator in which calls to
     * {@link java.util.Spliterator#trySplit()} always return {@code null}.
     *
     * @return an empty spliterator
     * @since 1.8
     */
    public Spliterator<E> spliterator() {
        return Spliterators.emptySpliterator();
    }

    /**
     * Returns a zero-length array.
     * @return a zero-length array
     */
    public Object[] toArray() {
        return new Object[0];
    }

    /**
     * Sets the zeroeth element of the specified array to {@code null}
     * (if the array has non-zero length) and returns it.
     *
     * @param a the array
     * @return the specified array
     * @throws NullPointerException if the specified array is null
     */
    public <T> T[] toArray(T[] a) {
        if (a.length > 0)
            a[0] = null;
        return a;
    }

    /**
     * @throws UnsupportedOperationException {@inheritDoc}
     * @throws ClassCastException            {@inheritDoc}
     * @throws NullPointerException          {@inheritDoc}
     * @throws IllegalArgumentException      {@inheritDoc}
     */
    public int drainTo(Collection<? super E> c) {
        if (c == null)
            throw new NullPointerException();
        if (c == this)
            throw new IllegalArgumentException();
        int n = 0;
        for (E e; (e = poll()) != null;) {
            c.add(e);
            ++n;
        }
        return n;
    }

    /**
     * @throws UnsupportedOperationException {@inheritDoc}
     * @throws ClassCastException            {@inheritDoc}
     * @throws NullPointerException          {@inheritDoc}
     * @throws IllegalArgumentException      {@inheritDoc}
     */
    public int drainTo(Collection<? super E> c, int maxElements) {
        if (c == null)
            throw new NullPointerException();
        if (c == this)
            throw new IllegalArgumentException();
        int n = 0;
        for (E e; n < maxElements && (e = poll()) != null;) {
            c.add(e);
            ++n;
        }
        return n;
    }

    /*
     * To cope with serialization strategy in the 1.5 version of
     * SynchronousQueue, we declare some unused classes and fields
     * that exist solely to enable serializability across versions.
     * These fields are never used, so are initialized only if this
     * object is ever serialized or deserialized.
     */

    @SuppressWarnings("serial")
    static class WaitQueue implements java.io.Serializable { }
    static class LifoWaitQueue extends WaitQueue {
        private static final long serialVersionUID = -3633113410248163686L;
    }
    static class FifoWaitQueue extends WaitQueue {
        private static final long serialVersionUID = -3623113410248163686L;
    }
    private ReentrantLock qlock;
    private WaitQueue waitingProducers;
    private WaitQueue waitingConsumers;

    /**
     * Saves this queue to a stream (that is, serializes it).
     * @param s the stream
     * @throws java.io.IOException if an I/O error occurs
     */
    private void writeObject(java.io.ObjectOutputStream s)
        throws java.io.IOException {
        boolean fair = transferer instanceof TransferQueue;
        if (fair) {
            qlock = new ReentrantLock(true);
            waitingProducers = new FifoWaitQueue();
            waitingConsumers = new FifoWaitQueue();
        }
        else {
            qlock = new ReentrantLock();
            waitingProducers = new LifoWaitQueue();
            waitingConsumers = new LifoWaitQueue();
        }
        s.defaultWriteObject();
    }

    /**
     * Reconstitutes this queue from a stream (that is, deserializes it).
     * @param s the stream
     * @throws ClassNotFoundException if the class of a serialized object
     *         could not be found
     * @throws java.io.IOException if an I/O error occurs
     */
    private void readObject(java.io.ObjectInputStream s)
        throws java.io.IOException, ClassNotFoundException {
        s.defaultReadObject();
        if (waitingProducers instanceof FifoWaitQueue)
            transferer = new TransferQueue<E>();
        else
            transferer = new TransferStack<E>();
    }

    // Unsafe mechanics
    static long objectFieldOffset(sun.misc.Unsafe UNSAFE,
                                  String field, Class<?> klazz) {
        try {
            return UNSAFE.objectFieldOffset(klazz.getDeclaredField(field));
        } catch (NoSuchFieldException e) {
            // Convert Exception to corresponding Error
            NoSuchFieldError error = new NoSuchFieldError(field);
            error.initCause(e);
            throw error;
        }
    }

}
